package offer.offer02;

import java.util.*;

/**
 * 当时还很菜。
 * 知识点: List和数组之间的转换, int[] 和Integer[] 之间的转换
 * 使用dequeue进行层序遍历, 转换的话就使用for循环吧, 没想到还挺快。
 */
public class S32I从上到下打印二叉树 {
    public int[] levelOrder(TreeNode root) {
        long time1 = System.currentTimeMillis();

        Deque<TreeNode> nodeList = new LinkedList<>();
        if(root != null) nodeList.add(root);
        List<Integer> result = new ArrayList<>();
        while(!nodeList.isEmpty()){
            TreeNode tmpNode = nodeList.getFirst();
            result.add(tmpNode.val);
            if(tmpNode.left != null) nodeList.add(tmpNode.left);
            if(tmpNode.right != null) nodeList.add(tmpNode.right);
            nodeList.removeFirst();
        }
//        try {
//            Thread.sleep(12);
//        } catch (InterruptedException e) {
//            e.printStackTrace();
//        }
        long time2 = System.currentTimeMillis();
        System.out.println("时间一: " + (time2 - time1));
        //这个转换操作非常耗时, 与之相比, 上面的操作耗时可以忽略不计
//        int[] result2 = result.stream().mapToInt(Integer::valueOf).toArray();
        int[] result2 = new int[result.size()]; // 直接数一下长度然后创建数组反而简单。
        for(int i = 0; i < result.size(); i ++){
            result2[i] = result.get(i);
        }
        long time3 = System.currentTimeMillis();
        System.out.println("时间二: " + (time3 - time2));
        return result2;
//        int[] result2 = new int[result.size()];
//        result2 = (int[]) result.toArray();
//        return result.toArray(result2);
    }

    // 猛男, 要不先数一下数的节点数量, 然后遍历塞进去?
    public int[] levelOrder2(TreeNode root) {
        if(root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};// 初始代码块?
        ArrayList<Integer> ans = new ArrayList<>();
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }


    public static void main(String[] args) {
        TreeNode input = new TreeNode(1);
        input.left = new TreeNode(2);
        input.right = new TreeNode(3);
        input.left.left = new TreeNode(4);
        input.left.right = new TreeNode(5);
        input.right.right = new TreeNode(7);
        input.left.left.left = new TreeNode(9);
        input.left.left.right = new TreeNode(10);
//        int[] result = new Solution32().levelOrder(input);
//        for(int i : result){
//            System.out.print(i + " ");
//        }
    }
}
